package 力扣;

import java.util.Arrays;

/**
 * @author ZhuYi
 * @create 2024/12/18 23:24
 */
public class 交易逆序对的总数_LCR170 {
    public static void main(String[] args) {
        int[] record = {7, 5, 6, 4};
        System.out.println(reversePairs(record));
    }

    public static int reversePairs(int[] record) {
        return mergeSort(0, record.length - 1, record);
    }

    static int mergeSort(int l, int r, int[] arr) {
        if (l >= r) return 0;
        int mid = (l + r) / 2;
        int res = 0;
        res += mergeSort(l, mid, arr) + mergeSort(mid + 1, r, arr);

        int i = l, j = mid + 1, k = 0;
        int[] tmp = new int[r - l + 1];
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
                res += mid - i + 1;
            }
        }

        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];

        for (i = l, j = 0; i <= r; i++, j++) {
            arr[i] = tmp[j];
        }
        return res;
    }
}
